package main

import (
	"fmt"
	"strings"
)

//func checkInclusion(s1 string, s2 string) bool {
//	//1 构建map
//	need := make(map[string]int)
//	for _, item := range s1 {
//		//fmt.Printf("%T %v\n", string(item), string(item))
//		if _, exist := need[string(item)]; exist {
//			need[string(item)]++
//			continue
//		}
//		need[string(item)] = 1
//	}
//
//	//2 初始化窗口指针
//	left, right := 0, 0
//
//
//	for {
//		if right >= len(s2) {
//			break
//		}
//		//3 扩大窗口 右移右指针
//		toBeAddedIn := string(s2[right])
//		right++
//		//fmt.Printf("%T %v\n", s2[right], string(s2[right]))
//
//		//4 缩小窗口 左移指针
//		for {
//			//判断是否需要缩小窗口
//			//即是否包含了全部字符
//			//if {}
//		}
//		break
//	}
//	return false
//}

func checkInclusion(s1 string, s2 string) bool {
	//1 构建map
	need := make(map[string]int)
	windows := make(map[string]int)
	for _, item := range s1 {
		//fmt.Printf("%T %v\n", string(item), string(item))
		if _, exist := need[string(item)]; exist {
			need[string(item)]++
			continue
		}
		need[string(item)] = 1
	}

	//2 初始化窗口指针
	left, right := 0, 0
	valid := 0
	for {
		if right >= len(s2) {
			break
		}
		//3 扩大窗口 右移右指针
		toBeAddedIn := string(s2[right])
		right++

		if find := strings.Contains(s1, toBeAddedIn); find {
			windows[toBeAddedIn]++
			if windows[toBeAddedIn] == need[toBeAddedIn] {
				valid++
			}
		}

		//4 缩小窗口 左移指针
		//判断是否需要缩小窗口
		for {
			if right-left < len(s1) {
				break
			}

			if valid == len(need) {
				return true
			}

			toBeMovedOut := string(s2[left])
			left++

			if find := strings.Contains(s1, toBeMovedOut); find {
				if windows[toBeMovedOut] == need[toBeMovedOut] {
					valid--

				}
				windows[toBeMovedOut]--
			}
		}

	}
	return false
}

func main() {
	s1 := "hello"
	s2 := "ooolleoooleh"
	fmt.Println(checkInclusion(s1, s2))
}
